
import java.util.HashSet;
import java.util.List;
import java.util.Set;
class SolutionZsh {
    public boolean wordBreak(String s, List<String> wordDict) { 
        Set<String> wordSet = new HashSet<>(wordDict);
        boolean[] result = new boolean[s.length()];
        for (int i = 1; i < result.length + 1; i++) {
            for (int j = 0; j < i; j++) {
                if ((j == 0 && wordSet.contains(s.substring(0 , i))) 
                || (j != 0 && result[j-1] && wordSet.contains(s.substring(j , i)))) {
                    result[i - 1] = true; 
                }
            }
        }
        return result[s.length() - 1];
    }
}